// https://www.lintcode.com/problem/merge-intervals/my-submissions
// 156. Merge Intervals
// Given a collection of intervals, merge all overlapping intervals.

// Example
// Given intervals => merged intervals:

// [                     [
//   (1, 3),               (1, 6),
//   (2, 6),      =>       (8, 10),
//   (8, 10),              (15, 18)
//   (15, 18)            ]
// ]
// Challenge
// O(n log n) time and O(1) extra space.


/**
 * Definition of Interval:
 * classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this->start = start;
 *         this->end = end;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param intervals: interval list.
     * @return: A new interval list.
     */
    
    static bool cmp(const Interval a, const Interval b)
    {
        return (a.start < b.start);            
    }
     
    vector<Interval> merge(vector<Interval> &intervals) {
        // 法一：个（错误，开区间）
        // int keep[1000]; 不是默认初始化为0
        // int keep[1000] = {0};
        // vector<Interval> result;
        // for (int i = 0; i < intervals.size(); i++)
        // {
        //     for (int j = intervals[i].start; j <= intervals[i].end; j++)
        //     {
        //         keep[j] = 1;
        //     }
        // }
        // for (int i = 0; i < 1000;)
        // {
        //     if (keep[i] == 1)
        //     {
        //         int start = i;
        //         while (keep[i] == 1)
        //         {
        //             i++;
        //         }
        //         int end = i - 1;
        //         // result.push_back(new Interval(start, end));
        //         result.push_back(Interval(start, end));
        //     }
        //     else
        //     {
        //         i++;
        //     }
        // }
        // return result;
        
    // 法二
    // • 直接合并，比如[1,3] [2,6] 合并成[1,6] ，不断合并，直到不能合并为止
    // • 区间左端点从小到大排个序
        vector<Interval> ans;
        if (intervals.empty())
        {
            return ans;    
        }
        sort(intervals.begin(), intervals.end(), cmp);
        ans.push_back(intervals[0]);
        // for (int i = 0; i < intervals.size(); i++)
        for (int i = 1; i < intervals.size(); i++)
        {
            if (intervals[i].start <= ans.back().end)
            {
                ans.back().end = max(intervals[i].end, ans.back().end);
            }
            else
            {
                ans.push_back(intervals[i]);
            }
        }
    }
};